package com.shi.data_structure.linked_list;

import java.util.Iterator;
import java.util.function.Consumer;

public class SinglyLinkedList implements Iterable<Integer>{
    private Node head;

    private static class Node{
        int value;
        Node next;

        public Node(int value, Node next){
            this.value = value;
            this.next = next;
        }
    }

//    public void addFirst(int value){
//        //链表为空
//        if (this.head == null) {
//            this.head = new Node(value, null);
//        }else{
//        //链表非空
//        this.head = new Node(value, this.head);
//        }
//    }

    public void addFirst(int value){
        this.head = new Node(value, this.head);
    }

    /**
     * while循环遍历
     * @param consumer
     */
    public void loop1(Consumer<Integer> consumer){
        Node cur = this.head;
        while (cur != null){
            consumer.accept(cur.value);
            cur = cur.next;
        }
    }

    /**
     * for循环遍历
     * @param consumer
     */
    public void loop2(Consumer<Integer> consumer){
        for (Node cur = this.head; cur != null; cur = cur.next){
            consumer.accept(cur.value);
        }
    }

    /**
     * 迭代器遍历
     * @return
     */
    @Override
    public Iterator<Integer> iterator(){
        //匿名内部类
        return new Iterator<Integer>() {
            Node cur = head;
            @Override
            public boolean hasNext() {
                return cur != null;
            }

            @Override
            public Integer next() {
                int v = cur.value;
                cur = cur.next;
                return v;
            }
        };
    }

    /**
     * 递归遍历
     * @param beforeConsumer
     * @param afterConsumer
     */
    public void loop3(Consumer<Integer>beforeConsumer,
                      Consumer<Integer>afterConsumer){
        recursion(this.head, beforeConsumer, afterConsumer);
    }

    /**
     * 递归函数
     * @param cur
     * @param beforeConsumer
     * @param afterConsumer
     */
    private void recursion(Node cur,
                           Consumer<Integer> beforeConsumer,
                           Consumer<Integer> afterConsumer){
        if(cur == null){
            return;
        }
        beforeConsumer.accept(cur.value);
        recursion(cur.next, beforeConsumer, afterConsumer);
        afterConsumer.accept(cur.value);
    }

    /**
     * 查找最后一个节点
     * @return
     */
    private Node findLast() {
        //空链表
        if(head == null){
            return null;
        }

        Node last = head;
        while (last.next != null){
            last = last.next;
        }

        return last;
    }

    /**
     * 向尾部添加
     * @param value
     */
    public void addLast(int value){
        //找到最后一个
        Node last = findLast();

        //空链表
        if(last == null){
            addFirst(value);
            return;
        }

        last.next = new Node(value, null);
    }

    /**
     * 向尾部添加多个
     * @param first
     * @param rest
     */
    public void addLast(int first, int... rest){
        //先穿成串
        Node sublist = new Node(first, null);
        Node cur = sublist;

        for (int value : rest) {
            cur.next = new Node(value, null);
            cur = cur.next;
        }

        //再插入
        Node last = findLast();

        if(last == null){
            this.head = sublist;
            return;
        }

        last.next = sublist;
    }

    /**
     * 根据索引获取节点的值
     * @param index
     */
    public int get(int index){
        Node node= findNode(index);

        //找到,返回值
        if(node != null){
            return node.value;
        }
        //没找到,抛异常
        throw illegalIndex(index);
    }

    /**
     * 抛出索引异常
     * @param index
     * @return
     */
    private static IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
    }

    /**
     * 查找节点
     * @param index
     * @return
     */
    private Node findNode(int index) {
        int i = 0;
        Node cur = head;
        for ( ; cur != null; cur = cur.next, i++){
            if(i == index){
                return cur;
            }
        }
        return null;
    }

    /**
     * 根据索引插入值
     * @param index
     * @param value
     */
    public void insert(int index, int value){
        //index == 0
        if(index == 0){
            addFirst(value);
            return;
        }

        //查找上一个节点
        Node prev = findNode(index - 1);
        //索引过大，上一个节点为空
        if(prev == null){
            throw illegalIndex(index);
        }

        //索引合法
        prev.next = new Node(value, prev.next);
    }

    /**
     * 根据索引删除值
     * @param index
     */
    public void remove(int index){
        //索引为0
        if(index == 0) {
            //链表非空
            if (head != null) {
                head = head.next;
                return;
            }else {
                //链表为空
                throw illegalIndex(index);
            }
        }

        //索引不为0
        Node prev = findNode(index - 1);
        Node cur = prev.next;
        if(prev != null && cur != null){
            prev.next = cur.next;
        } else {
            throw illegalIndex(index);
        }
    }

}
















